TODO
描述
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
1 | 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] |
提示:
- 1 <= arr.length <= 10^5
- -100 <= arr[i] <= 100
注意:本题与主站 53 题相同:https://leetcode-cn.com/problems/maximum-subarray/
分析
dp[i] 表示以 nums[i] 结尾的子数组最大值,dp[i] = max(nums[i], dp[i-1]+nums[i]), 这题跟 53 是一样的。
解决方案1(Python)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
numsLen = len(nums)
dp = [0] * numsLen
result = dp[0] = nums[0]
for i in range(1, numsLen):
dp[i] = max(nums[i], dp[i-1]+nums[i])
result = max(result, dp[i])
return result